#include <iostream>

template <class Type>
class BinarySearchTree {
public:
  void add(Type v) {
    if (root)
      this->privateAdd(root, v);
    else
      root = new Node(v);
  }

  void deleteNode(Type v) {
    if (this->privateDelete(NULL, this->root, v) == true)
      std::cout << "The item " << v << " was successfully removed" << std::endl;
    else
      std::cout << "The item " << v << " wasn't removed" << std::endl;
  }

  void print() {
    privatePrint(this->root);
    std::cout << std::endl;
  }

  void search(Type v) {
    if (privateSearch(this->root, v) == true)
      std::cout << "The item " << v << " is in the tree" << std::endl;
    else
      std::cout << "The item " << v << " is not in the tree" << std::endl;
  }

  BinarySearchTree() :root(NULL) {}

  ~BinarySearchTree() {
    deallocation(this->root);
  }

private:
  struct Node {
    Type value;
    Node* left;
    Node* right;

    Node(int v) : value(v), left(NULL), right(NULL) {}
  } *root;

  void deallocation(Node* current) {
    if (current == NULL) return;
    deallocation(current->left);
    deallocation(current->right);
    delete current;
  }

  void privateAdd(Node* current, Type v) {
    if (current->value > v) {
      if (!current->left)
        current->left = new Node(v);
      else
        privateAdd(current->left, v);
    } else {
      if (!current->right)
        current->right = new Node(v);
      else
        privateAdd(current->right, v);
    }
  }

  bool privateDelete(Node* parent, Node* current, Type v) {
    if (!current) return false;
    if (current->value == v) {
      if (current->left == NULL || current->right == NULL) {
        Node* temp = current->left;
        if (current->right) temp = current->right;
        if (parent) {
          if (parent->left == current) {
            parent->left = temp;
          } else {
            parent->right = temp;
          }
        } else {
          this->root = temp;
        }
      } else {
        Node* validSubs = current->right;
        while (validSubs->left) {
          validSubs = validSubs->left;
        }
        Type temp = current->value;
        current->value = validSubs->value;
        validSubs->value = temp;
        return privateDelete(current, current->right, temp);
      }
      delete current;
      return true;
    }
    return privateDelete(current, current->left, v) ||
           privateDelete(current, current->right, v);
  }

  void privatePrint(Node* current) {
    if (!current) return;
    privatePrint(current->left);
    std::cout << current->value << " ";
    privatePrint(current->right);
  }

  bool privateSearch(Node* current, Type v) {
    if (!current) return false;
    if (v == current->value) return true;
    if (v < current->value)
      return privateSearch(current->left, v);
    else
      return privateSearch(current->right, v);
  }
};

int main() {
  BinarySearchTree<int> tree;

  tree.add(11);
  tree.add(10);
  tree.add(6);
  tree.add(12);
  tree.add(15);
  tree.add(10);

  tree.print();
  tree.deleteNode(12);
  tree.search(6);
  tree.deleteNode(6);
  tree.print();
  tree.deleteNode(20);

  for (int i = 0; i < 30000; i++) {
    tree.add(i);
  }

  for (int i = 0; i < 30000; i++) {
    tree.deleteNode(i);
  }

  return 0;
}
